package LearnAlgorithm.d_标准查找算法and标准排序算法;

public class c2字符串匹配RabinKarpBy滚动哈希 {
	private static final long seed = 31;
	
	public static void main(String[] args) {
		String string = "ABAxBxABAxBxABAxBxABA";
		String keys = "ABA";
		long before = System.currentTimeMillis();
		rabinKrapMatch(string, keys);
		util.Util.duration(before);
	}
	
	/**
	 * O(M+N)
	 * 默认哈希的RabinKarp
	 * @param mother
	 * @param child
	 */
	public static void rabinKrapMatch(String mother, String child) {
		long childHashValue = hash(child);
		int length = child.length();
		long[] motherHashValues = hashOperate(mother, length);
		for (int i = 0; i < motherHashValues.length; i++) {
			if (motherHashValues[i] == childHashValue) {
				System.out.println("match begin:" + i + ", match end:" + (i + length - 1));
			}
		}
	}
	
	/**
	 * O(M)
	 * 滚动哈希
	 * 用滚动方法求出s中长度为n的每个子串的hash,组成一个hash数组
	 * @param mother
	 * @param childLength
	 * @return
	 */
	public static long[] hashOperate(String mother, int childLength) {
		long[] result = new long[mother.length() - childLength + 1];//定义存放mother中连续三个元素的哈希值的帮助数组；长度mother.length() - childLength + 1就是这么写，固定式子
		result[0] = hash(mother.substring(0, childLength));//添加帮助数组首个元素
		for (int i = childLength; i < mother.length(); i++) {//开始滚动；从第“childLength”个索引开始
			char current = mother.charAt(i);//定义要添加的字符
			char shouldBeDelete = mother.charAt(i - childLength);//定义要删去的字符
			//固定式子；举个例子hash(abcd) - a*31^4 = hash(bcd)；滚动就是这样
			long hashValue = (long) (result[i - childLength] * seed + (long) current - Math.pow(seed, childLength) * (long) shouldBeDelete) % Long.MAX_VALUE;
			result[i - childLength + 1] = hashValue;
		}
		return result;
	}
	
	/**
	 * 自定义hash算法
	 * 使100000个不同字符串产生的冲突数，大概在0~3波动，使用100百万不同的字符串， 冲突数大概110+范围波动。
	 * @param string
	 * @return
	 */
	public static long hash(String string) {
		long result = 0;
		for (int i = 0; i < string.length(); i++) {
			result = seed * result + (long) string.charAt(i);
		}
		return result % Long.MAX_VALUE;
		/*
		((0 + C0) * 31 + C1) * 31 + C2
		化简得：
		C0 * 31^2 + C1 * 31^1 + C2 * 31^0
		 */
	}
}
